{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Complete Tree Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #tree #binary-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #树 #二分查找 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完全二叉树的节点个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵<strong> 完全二叉树</strong> 的根节点 <code>root</code> ，求出该树的节点个数。</p>\n",
    "\n",
    "<p><a href=\"https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin\">完全二叉树</a> 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 <code>h</code> 层，则该层包含 <code>1~ 2<sup>h</sup></code> 个节点。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/14/complete.jpg\" style=\"width: 372px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,6]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目范围是<code>[0, 5 * 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>0 <= Node.val <= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li>题目数据保证输入的树是 <strong>完全二叉树</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>遍历树来统计节点是一种时间复杂度为 <code>O(n)</code> 的简单解决方案。你可以设计一个更快的算法吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-complete-tree-nodes](https://leetcode.cn/problems/count-complete-tree-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-complete-tree-nodes](https://leetcode.cn/problems/count-complete-tree-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6]', '[]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getLength(self, node, left = True):\n",
    "        ptr = node\n",
    "        count = 0\n",
    "        while ptr:\n",
    "            count += 1\n",
    "            if left:\n",
    "                ptr = ptr.left\n",
    "            else:\n",
    "                ptr = ptr.right\n",
    "        return count\n",
    "\n",
    "    def isCompleteTree(self, node):\n",
    "        n = self.getLength(node, True)\n",
    "        m = self.getLength(node, False)\n",
    "        \n",
    "        if n == m:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def countNodesFromCompleteTree(self, node):\n",
    "        return 2**self.getLength(node) - 1\n",
    "    \n",
    "    def countNodes(self, root: 'TreeNode') -> 'int':\n",
    "        if self.isCompleteTree(root):\n",
    "            return self.countNodesFromCompleteTree(root)\n",
    "        else:\n",
    "            return 1 + self.countNodes(root.left) + self.countNodes(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"        \n",
    "        d = {}\n",
    "        def find(node, t, i):\n",
    "            if node is None:\n",
    "                if t in d.keys():\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            \n",
    "            d.setdefault(t, 0)\n",
    "            d[t] = i\n",
    "            \n",
    "            if find(node.left, t + 1, i * 2):\n",
    "                return True\n",
    "            if find(node.right, t + 1, i * 2 + 1):\n",
    "                return True\n",
    "        \n",
    "        find(root, 0, 0)\n",
    "        \n",
    "        c = 0\n",
    "        \n",
    "        for i in range(len(d)):\n",
    "            if i < len(d) - 1:\n",
    "                c += 2 ** i\n",
    "            else:\n",
    "                c += d[i] + 1\n",
    "        \n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root: return 0\n",
    "        left = self.depth(root.left)\n",
    "        right = self.depth(root.right)\n",
    "        if left == right:\n",
    "            return 2**left + self.countNodes(root.right)\n",
    "        if left != right:\n",
    "            return 2**right + self.countNodes(root.left)\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        res = 0\n",
    "        while root:\n",
    "            res += 1\n",
    "            root = root.left\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        level = 0\n",
    "        li = [root]\n",
    "        while li:\n",
    "            length = len(li)\n",
    "            sign = 0\n",
    "            temp = []\n",
    "            for i in range(0,length):\n",
    "                if li[0] != None:\n",
    "                    tree = li.pop(0)\n",
    "                    temp.append(tree)\n",
    "                    li.append(tree.left)\n",
    "                    li.append(tree.right)\n",
    "                else:\n",
    "                    sign = 1\n",
    "            if sign == 1:\n",
    "                bottom_count = len(temp)\n",
    "                break\n",
    "            level +=1\n",
    "        print(level)\n",
    "        return 2**level -1 + bottom_count\n",
    "                \n",
    "                    \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: 'TreeNode') -> 'int':\n",
    "        nums = 0\n",
    "        d = getDepth(root)\n",
    "        if d == 0:\n",
    "            return 0\n",
    "        left = root.left\n",
    "        right = root.right\n",
    "        if getDepth(left) != getDepth(right):\n",
    "            nums = nums + 2**(d-2) + countNodes(left)\n",
    "        else:\n",
    "            nums = nums + 2**(d-1) + countNodes(right)\n",
    "        return nums\n",
    "\n",
    "def countNodes(root: 'TreeNode') -> 'int':\n",
    "        nums = 0\n",
    "        d = getDepth(root)\n",
    "        if d == 0:\n",
    "            return 0\n",
    "        left = root.left\n",
    "        right = root.right\n",
    "        if getDepth(left) != getDepth(right):\n",
    "            nums = nums + 2**(d-2) + countNodes(left)\n",
    "        else:\n",
    "            nums = nums + 2**(d-1) + countNodes(right)\n",
    "        return nums\n",
    "            \n",
    "def getDepth(root: 'TreeNode') -> 'int':\n",
    "    count = 0\n",
    "    while root is not None:\n",
    "        count += 1\n",
    "        root = root.left\n",
    "    return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        temp = []\n",
    "        if root:\n",
    "            temp.append(root)\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "        def node_search(li):\n",
    "            each_node = []\n",
    "            for node in li:\n",
    "                if node.left:\n",
    "                    each_node.append(node.left)\n",
    "                if node.right:\n",
    "                    each_node.append(node.right)\n",
    "            return each_node\n",
    "        flag = 1\n",
    "        while 1:\n",
    "            temp = node_search(temp)\n",
    "            if temp:\n",
    "                flag += len(temp)\n",
    "            else:\n",
    "                break\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def countNodes(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            inorder(node.left)\n",
    "            self.res.append(node.val)\n",
    "            inorder(node.right)\n",
    "            \n",
    "        inorder(root)\n",
    "        return len(self.res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            for i in range(len(stack)):\n",
    "                node = stack.pop(0)\n",
    "                res += 1\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        return 1 + self.countNodes(root.left) + self.countNodes(root.right) if root else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        self.count = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            self.count+=1\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        \n",
    "        def finddepth(root):\n",
    "            depth = 0\n",
    "            while root:\n",
    "                root = root.left\n",
    "                depth +=1\n",
    "            return depth\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        count = 0\n",
    "        while root:\n",
    "            ldepth = finddepth(root.left)\n",
    "            rdepth =  finddepth(root.right)\n",
    "            if ldepth == rdepth:\n",
    "                root = root.right\n",
    "                count+= 2**(ldepth)\n",
    "            else:\n",
    "                root = root.left\n",
    "                count+= 2**(rdepth)\n",
    "        \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        \"\"\"\n",
    "        @author: Suzy\n",
    "        @date: 2020-11-24\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        if not root.left and not root.right:\n",
    "            return 1\n",
    "\n",
    "        def getHeight(root):\n",
    "            if not root or (not root.left and not root.right):\n",
    "                return 0\n",
    "\n",
    "            return 1 + getHeight(root.left)\n",
    "        \n",
    "        \n",
    "        h = getHeight(root)\n",
    "        res = sum([pow(2, i) for i in range(h)])\n",
    "        q = [(root, 0)]\n",
    "        \n",
    "        while q:\n",
    "            t, d = q[0]\n",
    "            if d == h:\n",
    "                res += len(q)\n",
    "                break\n",
    "\n",
    "            q = q[1:]\n",
    "            if t.left:\n",
    "                q.append((t.left, d+1))\n",
    "            if t.right:\n",
    "                q.append((t.right, d+1))\n",
    "\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        res, queue = [], [(root, 0)]\n",
    "        if not root:\n",
    "            return 0\n",
    "        while queue:\n",
    "            cur, level = queue.pop(0)\n",
    "            if cur:\n",
    "                res.append(cur.val)\n",
    "                queue.append((cur.left, level + 1))\n",
    "                queue.append((cur.right, level + 1))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        l, r = root, root\n",
    "        h_l, h_r= 1, 1\n",
    "        while l.left:\n",
    "            l = l.left\n",
    "            h_l += 1\n",
    "        while r.right:\n",
    "            r = r.right\n",
    "            h_r += 1\n",
    "        \n",
    "        if h_l == h_r:\n",
    "            return 2**h_l - 1\n",
    "        \n",
    "        return self.countNodes(root.left) + self.countNodes(root.right) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countNodes(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.getdepth(root)\n",
    "    def getdepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        left_depth = self.getdepth(root.left)\n",
    "        right_depth = self.getdepth(root.right)\n",
    "        return 1 + left_depth + right_depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countNodes(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.countNodes(root.left)\n",
    "        right = self.countNodes(root.right)\n",
    "        return 1 + left + right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countNodes(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        path = [root]\n",
    "        lost = 0\n",
    "        flag = 0\n",
    "        while path[-1].right:\n",
    "            path.append(path[-1].right)\n",
    "            path[-2].right = None\n",
    "        ans = 2**len(path) - 1\n",
    "\n",
    "        n = len(path)\n",
    "\n",
    "        last = 0\n",
    "        while len(path):\n",
    "            if len(path) == n and path[-1].right:\n",
    "                return ans + 2**n - last\n",
    "            elif len(path) == n and path[-1].left:\n",
    "                return ans + 2**n -1 - last\n",
    "            elif len(path) == n:\n",
    "                last += 2\n",
    "                path.pop()\n",
    "            else:\n",
    "                if path[-1].right:\n",
    "                    path.append(path[-1].right)\n",
    "                    path[-2].right = None\n",
    "                elif path[-1].left:\n",
    "                    path.append(path[-1].left)\n",
    "                    path[-2].left = None\n",
    "                else:\n",
    "                    path.pop()\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = root.left\n",
    "        right = root.right\n",
    "        leftDepth = 0 #这里初始为0是有目的的，为了下面求指数方便\n",
    "        rightDepth = 0\n",
    "        while left: #求左子树深度\n",
    "            left = left.left\n",
    "            leftDepth += 1\n",
    "        while right: #求右子树深度\n",
    "            right = right.right\n",
    "            rightDepth += 1\n",
    "        if leftDepth == rightDepth:\n",
    "            return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2，所以leftDepth初始为0\n",
    "        return self.countNodes(root.left) + self.countNodes(root.right) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countNodes(self, root):\n",
    "        temp=root\n",
    "        if not root:\n",
    "            return 0\n",
    "        leftdepth,rightdepth=0,0\n",
    "        while root:\n",
    "            root=root.left\n",
    "            leftdepth+=1\n",
    "        while root:\n",
    "            root=root.right\n",
    "            rightdepth+=1\n",
    "        if leftdepth==rightdepth:\n",
    "            return 2**(leftdepth)-1\n",
    "        else:\n",
    "            l=self.countNodes(temp.left)\n",
    "            r=self.countNodes(temp.right)\n",
    "            return l+r+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countNodes(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        result = []\n",
    "        get_root = []\n",
    "        while True:\n",
    "            if result !=[] and get_root == []:\n",
    "                break\n",
    "            elif get_root == []:\n",
    "                result.append(root.val)\n",
    "                get_root.append(root.left)\n",
    "                get_root.append(root.right)\n",
    "            else:\n",
    "                new_root = []\n",
    "                for i in get_root:\n",
    "                    if i == None:\n",
    "                        continue\n",
    "                    result.append(i.val)\n",
    "                    new_root.append(i.left)\n",
    "                    new_root.append(i.right)\n",
    "                get_root = new_root.copy()\n",
    "        return len(result)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._ant = 0\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return\n",
    "        self._ant += 1\n",
    "        if node.left:\n",
    "            self.dfs(node.left)\n",
    "        if node.right:\n",
    "            self.dfs(node.right)\n",
    "        \n",
    "    def countNodes(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "        return self._ant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countNodes(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = root.left\n",
    "        right = root.right\n",
    "        leftDepth = 1 #这里初始为0是有目的的，为了下面求指数方便\n",
    "        rightDepth = 1\n",
    "        while left: #求左子树深度\n",
    "            leftDepth += 1\n",
    "            left = left.left\n",
    "        while right: #求右子树深度\n",
    "            rightDepth += 1\n",
    "            right = right.right\n",
    "            \n",
    "        # 题目说了是完全二叉树（不可能存在中间为空结点的情况），这里若是满二叉树\n",
    "        if leftDepth == rightDepth:\n",
    "            return 2**(leftDepth)-1\n",
    "            # return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2，所以leftDepth，rightDepth初始为0\n",
    "        return self.countNodes(root.left) + self.countNodes(root.right) + 1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
